package com.my.leetcode;

import java.util.*;

public class HashTableProblems {


    public static void main(String[] args) {

        HashTableProblems problems = new HashTableProblems();


        Hashtable<Integer, String> hashtable = new Hashtable<>();

        hashtable.put(1, null);

        int [] A= {1,2,4,4,8,16};
        System.out.println(problems.canReorderDoubled(A));
        System.out.println(problems.canReorderDoubled(new int []{-4,2,-2,4}));
    }


    /**
     * @author zlx
     * @Description 954. 二倍数对数组 middle
     * 给定一个长度为偶数的整数数组 A，只有对 A 进行重组后可以满足 “对于每个 0 <= i < len(A) / 2，都有 A[2 * i + 1] = 2 * A[2 * i]” 时，返回 true；否则，返回 false。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[3,1,3,6]
     * 输出：false
     * 示例 2：
     *
     * 输入：[2,1,2,6]
     * 输出：false
     * 示例 3：
     *
     * 输入：[4,-2,2,-4]
     * 输出：true
     * 解释：我们可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
     * 示例 4：
     *
     * 输入：[1,2,4,16,8,4]
     * 输出：false
     *
     *
     * 提示：
     *
     * 0 <= A.length <= 30000
     * A.length 为偶数
     * -100000 <= A[i] <= 100000
     * @Date 2020-09-29
     * @Param [A]
     * @return boolean
     **/
    public boolean canReorderDoubled(int[] A) {

        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < A.length;i++){
            if(!map.containsKey(A[i])){
                map.put(A[i], 1);
            }else{
                map.put(A[i], map.get(A[i]) + 1);
            }
        }

        Integer [] B= new Integer [A.length];
        for(int i = 0;i < A.length;i++){
            B[i] = A[i];
        }

        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o1) - Math.abs(o2);
            }
        };

        Arrays.sort(B, comparator);
        //Arrays.sort(B, (a,b) -> (Integer.compare( Math.abs(a),  Math.abs(b))));
        for(int b : B){
            if(map.get(b) <= 0){
                continue;
            }
            if(map.getOrDefault(b * 2, 0) <= 0){
                return false;
            }
            map.put(b, map.get(b) - 1);

            map.put(b * 2, map.get(b * 2) - 1);
        }
        return true;

    }
}
